package leetcode_day._2022._202208._1120;

/**
 * 1422. 分割字符串的最大得分
 *
 * @author yzh
 * @version 1.0
 * @date 2022/8/14 12:37
 */
public class _14 {

    public int maxScore_PrefixSum(String s) {
        int n = s.length();
        int[] sum = new int[n + 1];
        for (int i = 1; i <= n; i++) sum[i] += sum[i - 1] + (s.charAt(i - 1) - '0');
        int ans = 0;
        for (int i = 1; i < n; i++) {
            int a = i - sum[i], b = sum[n] - sum[i];
            ans = Math.max(ans, a + b);
        }
        return ans;
    }

    public int maxScore_Simulation(String s) {
        int n = s.length(), score = s.charAt(0) == '0' ? 1 : 0;
        for (int i = 1; i < n; i++) if (s.charAt(i) == '1') ++score;
        int ans = score;
        for (int i = 1; i < n - 1; i++) {
            if (s.charAt(i) == '0') ++score;
            else --score;
            ans = Math.max(ans, score);
        }
        return ans;
    }

}
